Corelab Seminar
2020-2021
Georgios Amanatidis
On the existence and approximation of EFX allocations
Abstract.
We consider the classic problem of fairly allocating indivisible goods among agents with additive valuation functions. We first explore the connection between maximum Nash welfare (MNW) and envy-freeness up to any good (EFX) and establish that an MNW allocation is always EFX if there are at most two possible values for the goods, whereas this is no longer true for three or more distinct values. As a notable consequence, this proves the existence of EFX allocations for this restricted class of valuation functions. We further present a novel algorithm for efficiently constructing EFX allocations in this setting. For general additive valuation functions, we propose a simple 0.618-approximation algorithm for computing EFX allocations which turns out to have good guarantees with respect to other fairness notions as well (EF1, MMS, PMMS, GMMS). We finally show that EFX allocations always exist when the number of goods does not exceed the number of agents by more than two.
This talk is based on:
G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, A. Hollender, A. A. Voudouris: Maximum Nash Welfare and Other Stories About EFX. Proceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020: 24-30 (2020)
and
G. Amanatidis, E. Markakis, A. Ntokos: Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theoretical Computer Science 841: 94-109 (2020)